#include <vector>
#include <iostream>
#include <algorithm>
#include <assert.h>
#include "list.h"
using namespace std;

//插入排序
void InsertSort(vector<int>& a)
{
	//[0,end]是有序的 现在插入的是 end+1这位数据
	//从后向前依次比较 查看插入位置

	for (int i = 0; i < a.size() - 1; i++)
	{
		//单趟
		int end=i;
		int tmp = a[end + 1];
		while (end >= 0)
		{
			if (tmp < a[end])
			{
				a[end + 1] = a[end];
				end--;
			}
			else
			{
				break;
			}
		}
		a[end + 1] = tmp;
	}
}

//希尔排序
void ShellSort(vector<int>& a)
{
	int gap = a.size();
	while (gap > 1)
	{
		gap = gap / 3 + 1;//保证gap最少是1
		for (int i = 0; i + gap < a.size(); i++)
		{
			int end = i;
			int tmp = a[end + gap];
			while (end >= 0)
			{
				if (tmp < a[end])
				{
					a[end + gap] = a[end];
					end -= gap;
				}
				else
				{
					break;
				}
			}
			a[end + gap] = tmp;
		}
	}
}


//选择排序
void SelectSort(vector<int>& a)
{
	if (a.empty()) return;
	int n = a.size();
	//begin 和 end是已经确定好排序的下标
	int begin = 0, end = n - 1;
	while (begin < end)
	{
		int mini = begin, maxi = end;
		for (int i = begin; i <= end; i++)
		{
			if (a[mini] > a[i])
			{
				mini = i;
			}
			if (a[maxi] < a[i])
			{
				maxi = i;
			}
		}
		swap(a[begin], a[mini]);
		if (maxi == begin)
		{
			maxi = mini;
		}
		swap(a[end], a[maxi]);
		++begin;
		--end;
	}
}




//堆排序
void AdjustDown(vector<int>& a ,int length,int starti)
{
	//找孩子
	int child = starti * 2 + 1;
	//最差结果就是把最后一个数也调整了
	while (child < length)
	{
		if (child + 1 < length && a[child] < a[child + 1]) child++;
		if (a[child] > a[starti])
		{
			swap(a[child], a[starti]);
			starti = child;
			child = starti * 2 + 1;
		}
		else
		{
			break;
		}
	}
}

void HeapSort(vector<int>& a)
{
	int n = a.size();
	int start = (n - 1 - 1) / 2;//找到最后一个非叶节点
	//依次向下调整
	for (int i = start; i >= 0; i--)
	{
		AdjustDown(a,n,i);
	}
	//建成了一个大堆 要弄成升序
	int end = n - 1;
	while (end > 0)
	{
		swap(a[0], a[end]);
		AdjustDown(a, end, 0);
		--end;
	}
}


//冒泡排序
//跟前一个比 你比我大 咱俩就交换 每过一轮就有一个当前的最大的值被换到数列尾，那么就可以少遍历一次。
void BubbleSort(vector<int>& a)
{
	int n = a.size();
	for (int j = 0; j < n - 1; j++) //轮次 4个数最多走三轮 剩下一个就自己确定了
	{
		int change = false;
		for (int i = 1; i < n - j; i++)
		{
			if (a[i-1] > a[i])
			{
				swap(a[i - 1], a[i]);
				change= true;
			}
		}
		if (!change) break; //如果一轮遍历下来 没有交换 就证明已经有序了
	}
}

//左闭右闭区间
void QuickSort(int arr[], int left, int right)
{
	if (left >= right) return;
	int key = arr[(left + right) / 2];//区间中间的那个值做key
	int i = left - 1;
	int j = right + 1;
	while (i < j)
	{
		//左找大
		do
		{
			i++;
		} while (arr[i] < key);
		

		//右找小
		do
		{
			j--;
		} while (arr[j]>key);

		if (i < j)
		{
			swap(arr[i], arr[j]);
		}
	}
	QuickSort(arr, left, j);
	QuickSort(arr, j + 1, right);
}

//template<class T1, class T2 >
//class Date 
//{
//public:
//	Date() { cout << "Date<class T1, class T2 >" << endl; }
//	T1 _a;
//	T2 _b;
//};
//
//template<>
//class Date<int, char>
//{
//public:
//	Date() { cout << " Date<int, char>" << endl; }
//	int _a;
//	char _b;
//};
//
//template<class T1,class T2>
//class Date<T1*,T2*>	
//{
//public:
//	Date() { cout << " Date<T1*,T2*>" << endl; }
//	T1 _a;
//	T2 _b;
//};
//void test2()
//{
//	Date<double, int> d1; // 调用特化的int版本
//	Date<int, char> d2; // 调用基础的模板
//	Date<int*, int*> d3; // 调用特化的指针版本
//	//Date<int&, int&> d4(1, 2); // 调用特化的指针版本
//}

void test_list1()
{
	chy::list<int> lt;
	lt.push_back(1);
	lt.push_back(2);
	lt.push_back(3);
	lt.push_back(4);
	lt.push_back(5);

	chy::list<int>::iterator it = lt.begin();
	cout << "目前正常" << endl;
	while (it != lt.end())
	{
		cout << *it << " ";
		++it;
	}
	cout << endl;

	it = lt.begin();
	while (it != lt.end())
	{
		*it *= 2;
		++it;
	}
	cout << endl;

	for (auto e : lt)
	{
		cout << e << " ";
	}
	cout << endl;
}


int main()
{
	//vector<int>a = { 7,10,67,234,56,111,3,99,2 };
	//int arr[] = { 7,10,67,234,56,111,3,99,2 };
	////SelectSort(a);
	////HeapSort(a);
	////InsertSort(a);
	////ShellSort(a);
	////BubbleSort(a);
	//int n = sizeof(arr) / sizeof(int);
	//QuickSort(arr, 0, n-1);
	////for (auto& e : arr) cout << e << " ";
	//for (int i = 0; i <n ; i++)
	//{
	//	printf("%d ", arr[i]);
	//}
	//cout << endl;
	//return 0;
	//test2();
	test_list1();
	return 0;
}